package 左哥算法.ch05链表;

import org.junit.Test;
import java.util.Stack;

public class Ch01回文链表与链表分区 {
    /**
     * 判断回文链表
     */
    @Test
    public void test01(){
        int[] arr={1,2,2,1};
        ListNode head=new ListNode(arr[0]),curr;
        curr=head;
        for (int i=1;i<arr.length;i++) {
            curr.next=new ListNode(arr[i]);
            curr=curr.next;
        }
//        ListNode a = new ListNode(0);
//        ListNode b = new ListNode(1);
//        ListNode c = new ListNode(0);
//        a.next=b;
//        b.next=c;
        System.out.println(onStack(head));
        System.out.println(onPointer(head));    //偷个懒，打断点去查看链表！！
    }

    /**
     * 方式一：使用栈
     * 将链表中的数据放入栈中，在通过依次出栈与链表的数据对比（因为栈是先进后出，相当于从后往前遍历链表）
     */
    public boolean onStack(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode curr=head;
        while (curr!=null){ //依次入栈
            stack.push(curr);
            curr=curr.next;
        }
        while (head!=null){
            if (head.val!=stack.pop().val){
                return false;
            }
            head=head.next;
        }
        return true;
    }

    /**
     * 方式二：快慢指针方式
     * 使用两个指针，一个每次走一步，一个每次走两步，但快指针走到末尾时慢指针走到链表中点
     * 将中点到末尾的这段链表反转，再遍历比较
     */
    public boolean onPointer(ListNode head){
        if (head==null||head.next==null){
            return true;
        }
        ListNode fast=head,slow=head;
//        while (fast.next!=null&&fast.next.next!=null){      //结束时慢指针走到中点或中点左侧
//            fast=fast.next.next;
//            slow=slow.next;
//        }
        while (fast!=null&&fast.next!=null){      //结束时慢指针走到中点或中点右侧
            fast=fast.next.next;
            slow=slow.next;
        }
//        slow=slow.next;
        ListNode endHead = reverse(slow);   //链表反转
        ListNode curr=endHead;  //将尾部头节点copy

        while (curr!=null){
            if (curr.val!=head.val){
                return false;
            }
            curr=curr.next;
            head=head.next;
        }
        reverse(endHead);
        return true;
    }

    public ListNode reverse(ListNode head){
        if (head==null||head.next==null){
            return head;
        }
        ListNode reverse = reverse(head.next);
        head.next.next=head;
        head.next=null;
        return reverse;
    }

    /**
     * 对链表进行分区，类似于快速排序的partition操作
     *题目：（力扣86）给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔
     * 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前
     * 应当 保留 两个分区中每个节点的初始相对位置。
     */
    @Test
    public void test02(){
        int[] arr={1,4,3,2,5,2};
        ListNode head=new ListNode(arr[0]),curr;
        curr=head;
        for (int i=1;i<arr.length;i++) {
            curr.next=new ListNode(arr[i]);
            curr=curr.next;
        }
        ListNode partition = partition(head, 3);
        System.out.println(partition);
    }

    /**
     * 对链表进行partition
     * 链表的partition操作是不会破稳定性的，因为链表的插入操作不需要互换位置
     * 方式一：将链表放入到数组中，对数组进行partition操作（不采用）
     * 方式二：采用4个变量，分别记录 小于区的起始节点和终止节点，以及大于区域其实节点和终止节点
     *      将大于x的值放入小于区域终止节点的next上
     */
    public ListNode partition(ListNode head,int x){
        ListNode start=null,end=null,bigStart=null,bigEnd=null;
        while (head!=null){
            if (head.val<x){    //放入小于部分
                if (start==null){   //如果左侧边界null
                    start=head;
                    end=head;
                }else {
                    end.next=head;
                    end=end.next;
                }
            }else {
                if (bigStart==null){    //如果右侧边界为null
                    bigStart=end==null?head:end.next;
                    bigEnd=bigStart;
                }else {
                    bigEnd.next=head;
                    bigEnd=bigEnd.next;
                }
            }
            head=head.next;
        }
        if (end!=null){     //两个区域连接
            end.next=bigStart;
        }
        if (bigEnd!=null){  //去尾操作，以免成为环形链表
            bigEnd.next=null;
        }
        return start!=null?start:bigStart;
    }
}
